1. Field
The present invention relates generally to cache and memory management and, more specifically, to code cache management for devices with a small memory footprint.
2. Description
Platform-independent programming languages such as Java and C# have gained significant market presence, especially for network-based applications. Typically, programs written in these languages are first compiled to codes in a platform-neutral distribution format called bytecodes. The bytecodes cannot directly run on any platform. They must be interpreted into instructions understandable by a specific platform. For Java programs, it is a Java Virtual Machine (JVM) that interprets bytecodes into instructions understood by the platform (for C# programs, Common Language Infrastructure (CLI) is the virtual machine). However, the interpretation by JVM usually imposes an unacceptable performance penalty for the execution of a bytecode because of the large runtime overhead processing required. A Just-In-Time (JIT) compiler has been designed to improve the JVM's performance. It compiles the bytecode of a given method into a native code of a platform before the method is first called. The native code of the method is stored in memory and any later calls to the method will be handled by this faster native code, instead of by the slower JVM's interpretation.
For devices with a small memory footprint, particularly mobile devices, a native code generated by a JIT compiler may be too big to fit in the memory. As a result, many manufacturers of such devices choose not to use JIT compilers and thus lose the performance advantage brought about by the JIT compilers. To use a JIT compiler for small memory devices, it is necessary to employ memory management mechanisms, which efficiently reuse memory space occupied by other native codes. When such memory management mechanisms are applied to a code cache where a native code is stored, they are usually referred to as Code Cache Management (CCM) mechanisms.
The issues of CCM are typically discussed as part of dynamic optimization problems, as discussed in “Code Cache Management Schemes for Dynamic Optimizers” by K. Hazelwood and M. D. Smith in the Proceedings of the Sixth Annual Workshop on Interaction between Compilers and Computer Architectures (INTERACT'02). One CCM scheme is Full Cache Flush (FCF). Under this scheme, upcoming codes begin filling a cache from the lowest address toward higher addresses. Once the cache is full, all the codes in the cache are flushed and the filling process is started again. Another CCM scheme is the Least-Recently Accessed Flush (LRAF), which flushes codes that have not been accessed recently when the cache is full. When the space freed by the least-recently accessed code is not enough to hold the upcoming code, the adjacent code(s) are flushed so that enough contiguous space can be made for the new code. Another CCM scheme is called Least-Frequently Accessed Flush (LFAF). The idea of LFAF is essentially the same as that of LRAF except that the least-frequently accessed code is the first candidate to be flushed. Yet another CCM scheme is Least-Recently Created Flush (LRCF) under which codes in a code cache are replaced in the same order as they are inserted. Yet another CCM scheme is Largest Element Flush (LEF), which first flushes the largest code (and the adjacent code(s) if more contiguous space is needed by the new code) to minimize the flush number. Yet another CCM scheme is the Best-Fit Element Flush (BFEF), which first flushes the code whose size is just enough (if not exactly same, then the smallest code whose size is larger than the new code size) for the new code.
When CCM schemes are applied to small memory systems running platform-independent programs (e.g., Java-like programs) with JIT compilers, recompilation rate of codes may increase. This is because a later code may call a previously compiled code that has already been flushed as a result of CCM. One goal of a CCM scheme for a small memory system running Java-like programs with a JIT compiler is to improve the efficiency of memory usage without significantly increasing the recompilation rate. Another goal is to reduce the overhead incurred by a CCM scheme because a large overhead can slow down the processing speed and thus compromises the possible performance improvement brought by the CCM scheme. The current available CCM schemes as mentioned above, however, can result in a higher recompilation rate and/or a large overhead, especially for small memory systems running Java-like programs. Therefore, a more efficient CCM scheme that can reduce the recompilation rate without adding much overhead is necessary to improve the performance of small memory systems running Java-like programs.